package com.masterlu.leetcode.daily.greedy.simple;

import java.util.HashMap;
import java.util.Map;

/**
 * 860. 柠檬水找零
 * https://leetcode-cn.com/problems/lemonade-change/
 * @date created in 2021/6/4 10:32
 */
public class S860LemonadeChange {


    public static void main(String[] args) {
        int[] bills = new int[]{5, 5, 5, 10, 20};
        lemonadeChange(bills);
    }

    public static boolean lemonadeChange(int[] bills) {

        Map<Integer, Integer> elementMap = new HashMap<>();
        elementMap.put(5, 0);
        elementMap.put(10, 0);

        for (int bill : bills) {
            if (bill == 5) {
                //5美分加一
                initMap(elementMap, bill);
            } else if (bill == 10) {
                if (elementMap.isEmpty() || elementMap.get(5) == 0) {
                    return Boolean.FALSE;
                }
                initMap(elementMap, bill);
                //5美分减一
                int newCount = elementMap.get(5) - 1;
                elementMap.put(5, newCount);
            } else if (bill == 20) {
                if (elementMap.get(5) >= 3 || (elementMap.get(5) > 0 && elementMap.get(10) > 0)) {
                    if (elementMap.get(10) > 0) {
                        //10美分、5美分减一
                        int newCount5 = elementMap.get(5) - 1;
                        elementMap.put(5, newCount5);
                        int newCount10 = elementMap.get(10) - 1;
                        elementMap.put(10, newCount10);
                    } else {
                        //5美分减3
                        int newCount5 = elementMap.get(5) - 3;
                        elementMap.put(5, newCount5);
                    }
                } else {
                    return Boolean.FALSE;
                }
            }
        }

        return Boolean.TRUE;
    }

    private static void initMap(Map<Integer, Integer> elementMap, int bill) {
        Integer element = elementMap.get(bill);
        element += 1;
        elementMap.put(bill, element);

    }

    public boolean lemonadeChange2(int[] bills) {

        int five = 0;
        int ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five <= 0) {
                    return Boolean.FALSE;
                }
                ten++;
                five--;
            } else if (bill == 20) {
                if (five > 3 || (ten > 0 && five > 0)) {
                    if (ten > 0) {
                        ten--;
                        five--;
                    } else {
                        five -= 3;
                    }
                } else {
                    return Boolean.FALSE;
                }
            }
        }

        return Boolean.TRUE;
    }


    public boolean lemonadeChange3(int[] bills) {

        int five = 0;
        int ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                ten++;
                five--;
            } else if (ten > 0) {
                ten--;
                five--;
            } else {
                five -= 3;
            }

            if (five < 0) {
                return Boolean.FALSE;
            }
        }

        return Boolean.TRUE;
    }
}
